128. Longest Consecutive Sequence

Hard

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

1
2
3

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solution

set (hashmap)

因为要保证O(n)的时间复杂度，所以可以使用set先来保存一下list。这样对每个元素的查询就都是O(1)的时间。

当想要知道最长的连续元素时，我们需要先取n，然后找他的n-1, n+1在不在set中，但这样难免出现重复查找的情况，比如一串数字3456，无论n遍历到哪一个数字，都会把其他的再查一遍，为了减少这种情况的出现。我们不如直接找到这串数字的开头，也就是3。如何找呢？我们就去找2，也就是（n-1）在不在set中，不在，那3肯定就是开头，那代码也就能出来了，凡是遍历n时n-1在set中，那就直接跳过，只去寻找那些是开头的数字后面到底跟了多少数。结果取最长的

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        ans = 0
        for x in nums:
            if x-1 not in nums:
                y = x+1
                while y in nums:
                    y += 1
                ans = max(ans, y-x)
        return ans